package 力扣;

import Tree.Employee;

/**
 * @author yyq
 * @create 2022-04-20 14:18
 */
public class leetcode669 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(2);
        root.right=new TreeNode(4);
        root.left.left=new TreeNode(1);
        trimBST(root,4,5);
    }
    public static TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null) return null;
        if(root.val<low||root.val>high){
            if(root.left==null&&root.right==null)
                return null;
        }
        TreeNode[] treeRoot=new TreeNode[1];
        preOrder(treeRoot,null,root,low,high);
        return treeRoot[0];
    }


    private static void  preOrder(TreeNode[] treeRoot,TreeNode pre, TreeNode root, int low, int high) {

        TreeNode temproot = null;
        int k = 0;

        if(root.val<low||root.val>high){
            k = 1;
            TreeNode left=root.left;
            TreeNode right=root.right;
            if(right==null&&left!=null){
                temproot = left;
            }else if(right!=null){
                if(left==null){
                    temproot=right;
                }else{
                    TreeNode righttemp = right;
                    while (righttemp.left!=null){
                        righttemp = righttemp.left;
                    }
                    righttemp.left=left.right;
                    left.right=right;
                    temproot =left;
                }
            }
            // pre 为空
            if(pre==null){
                treeRoot[0] = temproot;
            }
            if(pre!=null){
                if(pre.val>root.val){
                    pre.left= temproot;
                }
                if(pre.val<root.val){
                    pre.right=temproot;
                }
            }
        }
        if(k==1&&temproot!=null)//修改了root节
            preOrder(treeRoot,pre, temproot, low, high);
        else {
            if(k==0&&root.left!=null)
                preOrder(treeRoot,root, root.left, low, high);
            if(k==0&&root.right!=null)
                preOrder(treeRoot,root, root.right, low, high);
        }
    }
}
